package 不同的二叉搜索树;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/6 15:31
 * @description:
 */
public class Solution {
    public int numTrees(int n) {
        // 这道题有点复杂，采用的是动态规划，需要理解树的三种情况
        // dp[3] = 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
        // 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
        // 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
        // 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
        // 所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

        // dp[i]的含义为：i个不同的元素，构建不同的搜索树的最大数量（只用关注树的形状）
        int[] dp = new int[n + 1];
        dp[0] = 1;  //  不能初始化为0，不然一相乘就是0，初始化为1 可以解释为，空树也是一颗二叉搜索树！
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 以 j 为头节点，dp[j-1]表示左子树的搜索树数量。dp[i]右子树的搜素树数量
//                System.out.print("以" + j + "为头节点,dp[" + j + "]:" + dp[i] + "。");
//                System.out.println("左子树有：" + dp[j - 1] + "右子树有：" + dp[i - j]);
                dp[i] += dp[j - 1] * dp[i - j];
            }
//            System.out.println(Arrays.toString(dp));
        }
        return dp[n];
    }
}
